/*
 * Copyright (C), 2015-2018
 * FileName: Solution083
 * Author:   zhao
 * Date:     2018/9/7 10:19
 * Description: 83. 删除排序链表中的重复元素
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredone;

/**
 * 〈一句话功能简述〉<br>
 * 〈83. 删除排序链表中的重复元素〉
 *
 * @author zhao
 * @date 2018/9/7 10:19
 * @since 1.0.1
 */
public class Solution083 {
  /**************************************
   * 题目
   给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

   示例 1:

   输入: 1->1->2
   输出: 1->2
   示例 2:

   输入: 1->1->2->3->3
   输出: 1->2->3
   **************************************/

  /**************************************
   *
   * 想法：
   *  循环，判断的数据是否已经出现过
   * 我的做法
   * 超过29.9%的测试案例
   * 总结：
   *  总的思路是没有问题的
   *  空值判断，
   * ***********************************/
  public ListNode deleteDuplicates(ListNode head) {

    ListNode nowNode = head;
    while (nowNode != null && nowNode.next != null) {
      if (nowNode.val >= nowNode.next.val) {
        nowNode.next = nowNode.next.next;
      } else {
        nowNode = nowNode.next;
      }
    }
    return head;
  }

  /**************************************
   * 比我好的答案
   *
   * ***********************************/
  public ListNode better(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode pre = head;
    ListNode next = head.next;
    int value = head.val;
    while (next != null) {
      if (value != next.val) {
        value = next.val;
        pre.next = next;
        pre = next;
        next = next.next;
      } else {
        next = next.next;
      }
    }
    pre.next = null;
    return head;
  }

  public void testDeleteDuplicates() {
    ListNode listNode1 = new ListNode(1);
    ListNode listNode2 = new ListNode(1);
    ListNode listNode3 = new ListNode(3);
    ListNode listNode4 = new ListNode(4);
    ListNode listNode5 = new ListNode(5);
    ListNode listNode6 = new ListNode(5);
    listNode1.next = listNode2;
    listNode2.next = listNode3;
    listNode3.next = listNode4;
    listNode4.next = listNode5;
    listNode5.next = listNode6;
    ListNode listNode = deleteDuplicates(listNode1);
    System.out.println(listNode);

  }

  // Definition for singly-linked list
  class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }

    @Override
    public String toString() {
      StringBuilder sb = new StringBuilder();
      sb.append(val);
      if (next != null) {
        sb.append("->");
        sb.append(next.toString());
      }
      return sb.toString();
    }
  }

}
